package dp.子序列;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 判断子序列392.java
 * @createTime 2024年03月29日 17:30:00
 */
public class 判断子序列392 {
	/*
  dp[i][j]表示字符串s的前i,是否是字符串t的前j，的串
  如果 s(i)=t(j)
  dp(s,i,t,j)=dp(s,i-1,t,j-1)
  如果 s(i)!=t(j)
  dp(s,i,t,j)=dp(s,i,t,j-1);

  baseCase:
  dp[0][j]=true
  边界 s为空返回true
   */
	public boolean isSubsequence(String s, String t) {
		if (s.length() == 0) {
			return true;
		}
		int m = s.length();
		int n = t.length();
		boolean[][] dp = new boolean[m + 1][n + 1];
		for (int j = 0; j < n; j++) {
			dp[0][j] = true;
		}
		for (int i = 1; i <= m; i++) {
			for (int j = i; j <= n; j++) {
				if (s.charAt(i - 1) == t.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
		return dp[m][n];
	}
}
